2021 알고리즘 중간고사 - 봄

(1) 시험시간 : 4월 19일(월요일) 오전 8시 30분 - 10시 20분

(2) 풀이 중간과정을 충분히 기술하여 채점자에게 도움이 되도록 하세요.

풀이 과정이 충분하지 않거나 최종 답만 적으면 감점됩니다.

(3) 뒷면에 답을 쓰게 되면 작성자가 이 사실을 표시하기 바랍니다.

학번	이름	감독자 확인

문제 (배점)	점수	문제 (배점)	점수
1 (20)		4 (40)
2 (40)		5 (30)
3 (30)		6 (40)
		총합계 (200)

[1] Compute the closed form or asymptotic function for the followings. (20점)

[eqn: T(``1)=```1# T(`n)=``T``(`n/2`)+`n-1]

A: [eqn: 2n-log_{2}n-1]

Order는 맞지만 계산과정이 틀리거나 [eqn: 2^k leq n < 2^{k+1]로 해서 목조르기를 하여 일반적인 n에 대하여 설명을 하지 않은 경우 약간의 감점을 함.

큰 감점의 전형적인 경우

T(n)=T(n/2) +n-1 = T(n/4) + (n-1) + (n-1) = T(n/8) + (n-1) + (n-1)+(n—1)

또는 –1을 Log N번 더하지 않은 경우에는 약간의 감점

[2] (a) basic_operation( )의 수행 횟수를 f(N)의 asymptotic order로 제시하시오.

단, 계산과정이 최대한 자세히 기술되어야 한다. 답만 적으면 안됨. (20점)

while( N >= 2  ) :

if N%2 == 0 :

N = N // 2  # C N=N/2;

else :

N = N + 1

basic_operation( ) ;

print("N=", N )

조금 요상한 loop. N이 짝수면 N은 반으로 줄어들고 홀수면 1 증가. 따라서 +1증가되는 경우 홀수의 경우 다음에는 반드시 반으로 줄어드는 짝수의 경우가 생김. 따라서 훌수가 되는 경우는 최대 짝수와 같음,. 즉 홀수가 연이어 나타나는 경우는 없으므로 +1증가되는 경우는 최대 O(lon N)번임. 따라서 그 bound는 logN 이므로 order는 [eqn: Theta]( log N)

b)  basic_operation( )의 수행 횟수를 f(N)의 asymptotic order로 제시하시오.

단,  계산과정이 최대한 자세히 기술되어야 한다. 답만 적으면 안됨. (20점)

while( N >= 2  ) :

T = 1

while( T < N ) :

basic_operation()

T = T*2

#--- end of inner while ---

N = N//2    # N=N/2

A: [eqn: O((log _{2} N) ^{2})]

수식없이 order만 제시한 경우 감점.

[3]   항아리(Jug)에 검은색의 돌(B)과 흰색 돌(W)이 들어있다. 우리는 이 항아리에서 2개의 돌을 무작위로 꺼낸다. 만일 꺼낸 돌 2개 모두가 같은 색, 즉 모두가 검은색(B)이거나 흰색(W)이면 둘 모두를 버리고 외부에서 추가로 검은 돌을 하나 항아리에 추가한다(추가할 검은색 돌은 충분히 있다고 가정한다). 만일 꺼낸 돌 2개의 색이 각각 다르다면(즉 흰색(B), 검은색(W)이라면) 흰색 돌은 다시 항아리에 넣고, 검은색 돌만 버린다. 이 작업은 항아리에 돌이 1개만 남으면 중지한다.

Jug([eqn: b,w])는 항아리에 검은 색 돌 b개, 흰색 돌 w개가 있는 상황에서 제일 마지막에 남은 돌의 색이다. 예를 들어 [eqn: Jug(1`,`1)=w,```Jug(`0`,`2)=b]임을 알 수 있다.

a) 다음의 값을 구하시오. (10점)

i)  Jug(1, 3) : W

ii)  Jug(9, 2) : B

iii) Jug(8, 10) : B

b) 위 작업(algorithm)은 반드시 finite step안에 종료됨을 증명하시오. (10점)

한번 작업할 때 마다 전체 돌의 갯수는 반드시 최소 1씩 감소하므로 전체 돌의 수의   N개 일 때 N번의 작업 이후 돌은 0으로 된다. 이 과정을 resursion 식으로 표시하면   가점을 줌. 식 없이 단순히 설명만 한 경우에는 약간의 감점

J(w,b) -> J(w-2,b+1)

-> J(w, b-1)

색이 다를 경우  J(w,b) -> J(w-1+1,b-1) -> J(w,b-1)

따라서 w은 항상 그대로이거나 –2 감소. 따라서 w가 짝수면 b, w가 홀수면 결국에는

w가 남게 됨.

c) Jug([eqn: n,m])을 계산하는 코드를 아래 python style로 작성하시오. (10점)

def jug(n,m):  # 0 <= n,m <= 1000

답은 맞지만 아주 복잡한 조건으로 코딩한 경우에는 약간의 감점

# return(“b”), return(“w”) 을 활용하여 결과를 확정

[4] 정렬되지 않은 무작위 순서의 배열 X[n]이 있다. 이 안에서 우리는 이 X[n]의 n개 원소 중에서 [eqn: k]번째로 작은 원소를 찾으려고 한다. Quick Sort에서 사용하는 Divide and Conquer 전략을 이용하면 위 작업을 좀 더 쉽게 할 수 있다. 단, array를 나누는 pivot 원소로는 각 subarray의 제일 첫 번째 원소를 선택하여 사용한다.

1) 이 작업을 위한 pseudo code를 제시하시오. 입력으로는 정수 [eqn: k]가 주어진다.

(단, 전체를 미리 정렬한 뒤에 k번째를 찾는 방법을 쓰면 안 된다. 0점 처리.

우리가 원하는 것은 전체 정렬이 아니라 [eqn: k]번째 원소 하나만 찾는 것이다.) (10점)

임의의 원소를 선택해서 그 원소를 중심으로 그보다 작은 원소, 큰 원소를 QuickSort에서와 같이 나눈다. 만일 이 원소를 중심으로 그 보다 작은 원소가 k-1라면 그 pivot이 정답. 아닐 경우에는 양쪽 중 하나를 선택하여 다시 recursive하게 찾기 작업을 함. 단 이 경우 오른쪽 큰 원소 쪽이면 그 순서(k번째)를 조정해야함., 작은 쪽 원소 갯수를 k에서 공제(빼야)해야 함.

2) 제시한 코드대로 아래 16개 원소 중에서 k= 14번째 원소를 찾는 과정을 보이고 이 과정에서 몇 번의 원소 간 비교 연산이 수행되었는지 보이시오. (15점)

(조금 틀려도 과정이 맞으면 점수를 최대한 줌.)

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
X[i]	27	63	45	33	15	13	9	19	20	48	5	11	52	43	37	25

아래 정렬된 순서에서 각 원소의 차례를 참고하시오.

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
P[i]	5	9	11	13	15	19	20	25	27	33	37	43	45	48	52	63

3) 기본동작을 배열의 두 원소를 비교하는 원소 간 비교 연산으로 정할 때 worst case의 시간 복잡도를 [eqn: THETA (f(N))] 함수로 제시하고 그것을 설명하시오. (15점)

제일 좋은 경우는 pivot이 정확하게 반으로 쪼개주는 경우. 이 경우 복잡도는

T(N)= N + T(N/2)

제일 거지같은 경우는 pivot이 한쪽으로 치우치게 쪼개는 경우, 그야말로 가장

최악은 선택한 pivot에 제일 크거나(제일 오른쪽 원소) 또는 작은 원소(제일 왼쪽)인

이 경우에는 아예 쪼개지를 못하므로 그 복잡도는

T(N)= N + T(N-1), 따라서 O(N^2)

[5] 유럽 배낭여행을 한다. 아래 표에서 bus[[eqn: i]]는 [eqn: i]-번째 일자에 버스를 타야 하는 횟수를 표시한 값이다. 다음 일정에 대하여 가장 작은 비용으로 여행하는 계획을 세우시오. (어떤 날에 어떤 표를 사야 하는지를 제일 아래 표에 구매할 ticketing 계획을 표시하시오.) [eqn: T`[``k`]]에는 그 [eqn: k]일까지의 최소 ticket 비용이 표시되어야 한다.

a) 1회권=2€, 1일권=5€, 3일권=11€ 일 때 [eqn: T`[``k`]]를 구하는 Dynamic Programming식을 제시하고 이 식을 이용해서 아래 [eqn: T`[``k`]]표를 채우는 과정을 보이시오. (15점)

k	1	2	3	4	5	6	7	8	9	10
bus	2	1	0	5	0	0	3	4	0	2
[eqn: T`[``k`]]	4	6	6	11	11	11	16	21	21	25

T[k] = max(

T[k-1] + bus[i] * 2,

T[k-1] + 5,

T[k-3] + 11 )

점화식이 틀리거나 표의 내용이 잘못된 경우 감점처리

b) 1회권=1€, 3일권=9€, 5일권=12€일 때, 5일권 1장, 3일권 1장, 1회권 2장이 최적인 경우의 상황을 구성하여 아래 표에 표시하시오. bus 행에 탑승 횟수를 0부터 9 사이의 숫자로 표시하고 각 표를 사용하는 기간을 구입표 행에 표시해야 한다. 그리고 왜 그것이 최적인지 설명해야 한다. (15점)

k	1	2	3	4	5	6	7	8	9	10	11
bus	9	9	9	9	9	9	9	9	0	1	1
구입표	5	-	-	-	-	3	-	-	X	1	1

5일권 내의 탑승 횟수가 12회 이상, 3일권 내의 탑승 횟수가 9회 이상이어야 함.

5일권 2개가 최적이 되는 경우나 5/3/3이 최적이 되는 경우 오답처리.

[6] 어느 공장에서 근무 계획을 세우려고 한다. 아래 표에서 [eqn: p _{i}]는 작업 [eqn: i]를 마쳤을 때 얻을 수 있는 이득이며 [eqn: d_i]는 작업 [eqn: i]의 마감 일자(deadline)를 나타낸다. 모든 task는 작업하는 데 1일이 걸린다. 아래 표에는 task 번호를 기록해야 한다.

task	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
[eqn: p _{i}]	40	35	30	29	25	24	20	18	16	16	15	12	10	8	7
[eqn: d _{i}]	2	2	1	3	2	1	4	2	3	4	3	2	3	2	2

a) 1개의 기계로 얻을 수 있는 최대 이득을 계산하시오. (10점)

	day1	day2	day3	day4
M1	1	2	4	7

: 124,

다른 순서도 기간과 결과값이 맞으면  인정

b) 만일 주어진 기계가 2대라면 얻을 수 있는 최대 이득을 계산하시오. (10점)

	day1	day2	day3	day4
M1	1	2	4	7
M2	3	5	9	10

: 211, 다른 순서도 기간과 결과값이 맞으면  인정

c) 1대 기계로 가능한 이익 중 2번째(second maximum)로 큰 값을 계산하고 그 이유를 설명하시오. (최대 이득보다 작은 값의 이득 중 가장 높은 값. 최적과 같으면 안됨.) (10점)

	day1	day2	day3	day4
M1	1	2	4	10

: 120, 다른 순서도 기간과 결과값이 맞으면  인정

d) 2대의 기계로 가능한 이익 중 2번째(second maximum)로 큰 값을 계산하고 그 이유를 설명하시오(즉, 최대 이득보다 작은 값의 이득 중 가장 높은 값. 최적과 같으면 안됨). (10점)

	day1	day2	day3	day4
M1	3	1	4	7
M2	6	2	9	10

: 210,

다른 순서도 기간과 결과값이 맞으면  인정, 3 1 4 7 5 2 11 10도 인정.